package com.zhj.algorithm.sort;

import java.util.Arrays;

/**
 * @PackageName:com.zhj.algorithm.sort
 * @ClassName:ShellSort
 * @auter: 朱慧杰
 * @date:2020/8/9 0009 16:50
 **/
public class ShellSort {

    // 希尔排序，解决插入排序最后位小移动次数多问题
    public static void main(String[] args) {
        int[] arr = new int[]{4,6,2,1,3,5,8,7,0};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void shellSort(int[] arr) {
        for (int d = arr.length/2; d > 0; d/=2) {
            for (int i = d; i < arr.length; i++) {
                for (int j = i-d; j >= 0; j-=d) {
                    if (arr[j] > arr[j+d]) {
                        int temp = arr[j];
                        arr[j] = arr[j+d];
                        arr[j+d] = temp;
                    }
                }
            }
        }
    }

}
